import random
import math
import _00GraphFuc as gf

#实现构造树
def createtree(m):
    Vt={0,1}
    Et={(0,1)}
    k=2
    for n in range(m-2):
        [i]=random.sample(list(Vt),1)
        Et=Et|{(i,k)}
        Vt=Vt|{k}
        k=k+1
    return [Vt,Et]

#判断是否为树
def istree(V,E):
    tv=True
    E=sorted(E)
    (u,v)=E[0]
    Vt={u,v}
    E=set(E)-{(u,v)}
    Et={(u,v)}
    while(E!= set({})):
        for (u,v) in E:
            if (u in Vt) and (v in Vt):
                tv=False
                break
            if ((u in Vt) and (v not in Vt))or ((u not in Vt) and (v in Vt)):
                Vt=Vt|{u,v}
                E=E-{(u,v)}
                Et=Et|{(u,v)}
        if(tv==False):
            break
    if((len(Vt)-1)!=len(Et)):
        tv=False 
    return tv

#创建二叉树：
def createbitree(nodes):
    nodes=set(nodes)
    if(len(nodes)==0):
        return []
    if(len(nodes)== 1):
        return list(nodes)
    [a]=random.sample(list(nodes),1)
    nodes = nodes-{a}
    k=random.randint(0,len(nodes)-1)
    Lnodes =random.sample(list(nodes),k)
    Lnodes=set(Lnodes)
    Rnodes = nodes-Lnodes 
    L=createbitree(Lnodes)
    R=createbitree(Rnodes)
    return [a,L,R]

def tree2graph(tree):
    gtree=set({})
    if len(tree) == 0| len(tree)== 1:
        return gtree
    if len(tree[1])!= 0:
        L=tree2graph(tree[1])
        gtree=gtree |{(tree[0],tree[1][0])}|L 
    if len(tree[2])!= 0:
        R=tree2graph(tree[2])
        gtree=gtree|{(tree[0],tree[2][0])}|R 
    return gtree

def bitree(nodes):
    nodes=list(nodes)
    if(len(nodes)== 0):
        return[]
    if(len(nodes)==1):
        return nodes
    k=int(len(nodes)/2)
    a=nodes.pop(k)
    Lnodes =nodes[0:k]
    Rnodes= nodes[k:]
    L=bitree(Lnodes)
    R=bitree(Rnodes)
    return [a,L,R]

#前序遍历
def preordertraversal(tree):
    if(len(tree)==0):
        return []
    if(len(tree)==1):
        return [tree[0]]
    else:
        return [tree[0]]+preordertraversal(tree[1])+preordertraversal(tree[2])

#中序遍历
def inordertraversal(tree):
    if(len(tree)==0):
        return []
    if(len(tree)==1):
        return [tree[0]]
    else:
        return inordertraversal(tree[1])+[tree[0]]+inordertraversal(tree[2])
    
#后序遍历
def postordertraversal(tree):
    if(len(tree)==0):
        return []
    if(len(tree)==1):
        return [tree[0]]
    else:
        return postordertraversal(tree[1])+postordertraversal(tree[2])+[tree[0]]
    
#霍夫曼树计算每个字符出现频率
def frequencylist(V):
    W0=[]
    s=0
    for u in V:
        w=random.randint(0,1000)
        W0=W0+[[w,u]]
        s=s+w
    W=[]
    for [w,u] in W0:
        w=math.floor((w/s)*10000)/10000
        W=W+[[w,u]]
    return W

#构建霍夫曼树
def Huffmantree(W):
    tree=sorted(W)
    while len(tree)!= 1:
        w=tree[0][0]+tree[1][0]
        w=math.floor(w*10000)/10000
        tree=[[w,tree[0],tree[1]]]+tree[2:]
        tree=sorted(tree)
    return tree[0]

#将霍夫曼树转变为图
def Huffmantree2graph(tree):
    gtree=set({})
    if len(tree)==2:
        return gtree
    L=Huffmantree2graph(tree[1])
    R=Huffmantree2graph(tree[2])
    a=math.floor(tree[0]*10000)/10000
    l=math.floor(tree[1][0] *10000)/10000 
    r=math.floor( tree[2][0]*10000)/10000 
    gtree= {(a,l)}|{(a,r)}|L|R
    return gtree

#霍夫曼编码
def huffmancoding(subtree,code):
    if len(subtree)==2:
        return [[ subtree[1],code]]
    else:
        node0=subtree[1]
        node1= subtree[2]
        code = huffmancoding(node0,code+'0')+huffmancoding(node1,code+'1')
    return code

def HuffmanCoding(tree):
    code0 =huffmancoding(tree[1],'0')
    code1=huffmancoding(tree[2],'1')
    return code0+code1

#计算熵与平均码长
def codingentropy(W,C):
    r0=0
    r=0
    W=sorted(W)
    C=sorted(C)
    for k in range(len(W)):
        r0-=W[k][0]* math.log2(W[k][0])
        r+=W[k][0]*len(C[k][1])
    r0=math.floor((r0)*1000)/1000 
    r=math.floor((r)*1000)/1000 
    return [r0,r]

#对任意G的连通子图，构造一棵树
def graph2tree(V,E):
    E=sorted(E)
    (u,v)=E[0]
    Vt={u,v}
    Et={(u,v)}
    E=set(E)
    n=len(V)
    while(len(Et)<(n-1)):
        m=len(Vt)
        for (u,v) in E:
            if((u in Vt and v not in Vt)
            or (u not in Vt and v in Vt)):
                Vt=Vt|{u,v}
                Et=Et|{(u,v)}
        E=E-Et
        if(m == len(Vt)):
            break 
    return [Vt,Et]

#普利姆算法
def Primspantree(V,E):
    E=sorted(E)
    [w,u,v]=E[0]
    Vt={u,v}
    Et={(w,u,v)}
    del E[0]
    n=len(V)
    while(len(Et)<(n-1)):
        i=0
        while(i < len(E)):
            [w,u,v]=E[i]
            if(u in Vt and v not in Vt)or(u not in Vt and v in Vt):
                Et=Et|{(w,u,v)}
                Vt=Vt|{u,v}
                del E[i]
                break
            i=i+1 
    return [Vt,Et]

#克鲁苏卡尔算法
def iscycled(V,E,u0,v0):
    tv=False
    Vc={u0,v0}
    Ec={(u0,v0)}
    n=0
    while(n != len(Vc)):
        n=len(Vc)
        for (w,u,v) in E:
            if((u in Vc) and (v in Vc)):
                tv= True
                return tv
            if (u in Vc and v not in Vc) or (u not in Vc and v in Vc):
                Ec=Ec |{(u,v)}
                Vc=Vc|{u,v} 
                E=E-{(w,u,v)}
                break
    return tv

def Kruskalspantree(V,E):
    E=sorted(E)
    Vt=set({})
    Et=set({})
    n=len(V)
    k=0

    i=0
    while(len(Et)<n-1):
        [w,u,v]=E[i]
        i=i+1
        if(((u in Vt) and (v in Vt))):
            if(iscycled(Vt,Et,u,v)):
                continue
        Et=Et|{(w,u,v)}
        Vt=Vt|{u,v}
    return [Vt,Et]